//#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//hhhhhhhhhhhhhhhhhhhhhhh
int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		string s;
		int K;
		cin >> s >> K;
		vector<int> v(26, 0);
		int start = 0, end = 0;
		long long count = 0;
		int size = 0;
		while (start<s.size())
		{
			if(end < s.size())
				size = ++v[(s[end] - 'a')];
			if (end < s.size() && size <= K)
			{
				end++;
			}
			else
			{
				while (end<s.size() && start < s.size() && s[start] != s[end])
				{				
					count += end - start;
					v[(s[start++] - 'a')]--;
				}
				count += (end - start);
				v[(s[start++] - 'a')]--;
				if (end < s.size())
					end++;
			}
		}
		cout << count << endl;

	}
	return 0;
}